Traditional routing protocols in wireless mesh networks often use a single route to deliver packets from a source node to a destination node. FIG. 1A is a diagram of an exemplary wireless mesh network 10 that illustrates a traditional routing approach. As shown in FIG. 1A, a route is established from a source node (S) 12 to a destination node (D) 14 via a single path through first and second relay nodes (R1 and R2) 16,18 (see, e.g., “DSR: The Dynamic Source Routing Protocol for Multi-Hop Wireless Ad Hoc Networks,” by Johnson et al., Ad Hoc Networking, Ed. C. E. Perkins Addison-Wesley, 2001, pp. 139-172; “Ad-Hoc On-Demand Distance Vector Routing,” by Perkins et al., Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, 1997, pp. 90-100; and “Better Approach to Mobile Ad-Hoc Networking” by Neumann et al., IETF Internet Draft). The route is established by finding the best next hop for a newly arrived packet based on different criteria (e.g., number of hops, delay, etc.). More recently, multi-path routing protocols have been developed for wireless networks that rely on sharing the load between different paths (see, e.g., “An Optimized Ad-Hoc On-Demand Multipath Distance Vector (AOMDV) Routing Protocol,” by Yuan et al., Asia-Pacific Conf on Communications, 2005). These routing approaches are similar to routing protocols used in wired networks and do not exploit the broadcast nature of the wireless medium. That is, the broadcast nature of the wireless medium enables the nodes to “overhear” packets transmitted to other nodes.
In contrast to traditional routing protocols in wireless networks, the ExOR protocol is an integrated routing and MAC technique that utilizes the cooperation between nodes using the broadcast nature of the wireless medium (see, e.g., “ExOR: Opportunistic Multi-Hop Routing for Wireless Networks,” by Biswas et al., SIGCOMM, 2005). In the ExOR protocol, the nodes in the network need to coordinate their actions to avoid transmitting duplicate packets. In order to decrease the coordination overhead between nodes, various protocols have exploited random linear network coding (RLNC) (see, e.g., “MORE: A Network Coding Approach to Opportunistic Routing,” by Chachulski et al., SIGCOMM, 2007; “CCACK: Efficient Network Coding Based Opportunistic Routing Through Cumulative Coded Acknowledgments,” by Koutsonikolas et al., IEEE INFOCOM, 2010; “GeoCode: A Geo-graphic Coding-Aware Communication Protocol,” by Khamfroush et al., International IEEE Conf. on Intel. Transp. Sys. (ITSC), 2011; and others). RLNC is a coding technique that allows a sender to transmit random linear combinations of a group of original packets (see, e.g., “A Random Linear Network Coding Approach to Multicast,” by Ho et al., IEEE Trans. on Inf. Theory, vol. 52, no. 10, 2006).
The MORE protocol is an opportunistic routing protocol that implements RLNC. Each relay will store coded packets for an active generation and re-code before sending (i.e., the relay will create new linear combinations based on the contents of its buffer of coded packets). Although MORE is interesting, its impact on commercial systems may take a while to realize because it lacks compatibility with standard routing protocols and because it relies on an offline calculation of the error probability of each link. The GeoCode protocol creates multiple paths by choosing nodes that are located inside a specified geographic area (e.g., an ellipse) as relay nodes. The created paths may intersect each other at intermediate nodes which use network coding to maximize the throughput. The CCACK protocol uses a Cumulative Coded acknowledgement approach to acknowledge network coded flow to upstream nodes, where the acknowledgement feedback is resilient to packet losses. None of these protocols work well with traditional routing protocols.
There is a need for techniques, systems, and protocols that are compatible with traditional routing protocols and that are capable of taking advantage of the broadcast nature of wireless networks to improve overall performance of a network.